論文の概要: Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithm
- arxiv url: http://arxiv.org/abs/2101.10506v1
- Date: Tue, 26 Jan 2021 01:12:07 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-14 15:14:20.697773
- Title: Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithm
- Title（参考訳）: 二時間スケール自然アクタークリティカルアルゴリズムの有限サンプル解析
- Authors: Sajad Khodadadian, Thinh T. Doan, Siva Theja Maguluri, Justin Romberg
- Abstract要約: アクタークリティカルな2時間スケールのアルゴリズムは強化学習で非常に人気がある。
本論文では,オンライン自然なアクター・クリティカルアルゴリズムのグローバル収束を特徴づける。
十分な探査を確保するために$epsilon$-greedyサンプリングを使用します。
- 参考スコア（独自算出の注目度）: 21.91930554261688
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Actor-critic style two-time-scale algorithms are very popular in
reinforcement learning, and have seen great empirical success. However, their
performance is not completely understood theoretically. In this paper, we
characterize the global convergence of an online natural actor-critic algorithm
in the tabular setting using a single trajectory. Our analysis applies to very
general settings, as we only assume that the underlying Markov chain is ergodic
under all policies (the so-called Recurrence assumption). We employ
$\epsilon$-greedy sampling in order to ensure enough exploration.
For a fixed exploration parameter $\epsilon$, we show that the natural actor
critic algorithm is $\mathcal{O}(\frac{1}{\epsilon T^{1/4}}+\epsilon)$ close to
the global optimum after $T$ iterations of the algorithm.
By carefully diminishing the exploration parameter $\epsilon$ as the
iterations proceed, we also show convergence to the global optimum at a rate of
$\mathcal{O}(1/T^{1/6})$.
- Abstract（参考訳）: アクタークリティカルな2時間スケールのアルゴリズムは強化学習で非常に人気があり、実証的な成功を収めている。
しかし、その性能は理論的に完全には理解されていない。
本論文では, 単一の軌道を用いて, タブラ設定におけるオンライン自然なアクター・クリティカルアルゴリズムのグローバル収束を特徴づける。
我々の分析は、マルコフ連鎖がすべての方針の下でエルゴード的であると仮定する(いわゆる再帰仮説)ので、非常に一般的な設定に当てはまる。
十分な探査を確保するために$\epsilon$-greedyサンプリングを使用します。
固定探索パラメータ $\epsilon$ に対して、自然作用素批判アルゴリズムは $\mathcal{O}(\frac{1}{\epsilon T^{1/4}}+\epsilon)$ であり、アルゴリズムの$T$繰り返しの後、世界最適に近いことを示した。
繰り返しが進むにつれて探索パラメータ $\epsilon$ を慎重に減らすことにより、$\mathcal{O}(1/T^{1/6})$ の速度で地球最適値への収束を示す。
関連論文リスト
- Improved Sample Complexity for Global Convergence of Actor-Critic Algorithms [49.19842488693726]
我々は,O(epsilon-3)$のサンプル複雑性を大幅に改善したアクター・クリティック・アルゴリズムのグローバル収束を確立した。
我々の発見は、一定のステップサイズに依存する多くのアルゴリズムに対する理論的支援を提供する。
論文 参考訳（メタデータ） (2024-10-11T14:46:29Z) - 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) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Finite-Time Analysis of Fully Decentralized Single-Timescale
Actor-Critic [4.94128206910124]
本稿では,アクタ,批評家,グローバル報酬推定器を交互に更新する,完全に分散化されたアクタ・クリティカル(AC)アルゴリズムを提案する。
このアルゴリズムは,Markovian サンプリングにおいて $tildemathcalO(epsilon-2)$ のサンプル複雑性を持つことを示す。
また、我々のアルゴリズムのローカルアクションプライバシ保護バージョンとその分析も提供する。
論文 参考訳（メタデータ） (2022-06-12T13:14:14Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。
提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。
我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文 参考訳（メタデータ） (2021-06-15T02:23:07Z) - Improved Sample Complexity for Incremental Autonomous Exploration in
MDPs [132.88757893161699]
我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。
DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
論文 参考訳（メタデータ） (2020-12-29T14:06:09Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。