論文の概要: Asynchronous Advantage Actor Critic: Non-asymptotic Analysis and Linear
Speedup
- arxiv url: http://arxiv.org/abs/2012.15511v1
- Date: Thu, 31 Dec 2020 09:07:09 GMT
- ステータス: 翻訳完了
- システム内更新日: 2021-04-17 16:57:49.458562
- Title: Asynchronous Advantage Actor Critic: Non-asymptotic Analysis and Linear
Speedup
- Title（参考訳）: 非同期アドバンテージアクター批判:非漸近解析と線形高速化
- Authors: Han Shen, Kaiqing Zhang, Mingyi Hong, Tianyi Chen
- Abstract要約: 本稿では、A3CアルゴリズムをTD(0)で修正し、A3C-TD(0)と呼ばれ、証明可能な収束を保証する。
i.i.d.
サンプリング a3c-td(0) は、作業者あたり $mathcalo(epsilon-2.5/n)$ のサンプル複雑性を取得して $epsilon$ 精度を達成する。
2 に対して $mathcalO(epsilon-2.5/N)$ の最もよく知られたサンプル複雑性との比較
- 参考スコア（独自算出の注目度）: 56.27526702716774
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Asynchronous and parallel implementation of standard reinforcement learning
(RL) algorithms is a key enabler of the tremendous success of modern RL. Among
many asynchronous RL algorithms, arguably the most popular and effective one is
the asynchronous advantage actor-critic (A3C) algorithm. Although A3C is
becoming the workhorse of RL, its theoretical properties are still not
well-understood, including the non-asymptotic analysis and the performance gain
of parallelism (a.k.a. speedup). This paper revisits the A3C algorithm with
TD(0) for the critic update, termed A3C-TD(0), with provable convergence
guarantees. With linear value function approximation for the TD update, the
convergence of A3C-TD(0) is established under both i.i.d. and Markovian
sampling. Under i.i.d. sampling, A3C-TD(0) obtains sample complexity of
$\mathcal{O}(\epsilon^{-2.5}/N)$ per worker to achieve $\epsilon$ accuracy,
where $N$ is the number of workers. Compared to the best-known sample
complexity of $\mathcal{O}(\epsilon^{-2.5})$ for two-timescale AC, A3C-TD(0)
achieves \emph{linear speedup}, which justifies the advantage of parallelism
and asynchrony in AC algorithms theoretically for the first time. Numerical
tests on synthetically generated instances and OpenAI Gym environments have
been provided to verify our theoretical analysis.
- Abstract（参考訳）: 標準強化学習(RL)アルゴリズムの非同期並列実装は、現代のRLの大きな成功の鍵となる。
多くの非同期rlアルゴリズムの中で、最も人気があり効果的なアルゴリズムはa3c(asyncer advantage actor-critic)アルゴリズムである。
A3C は RL のワークホースになりつつあるが、その理論的性質はまだよく理解されておらず、非漸近解析や並列性(a.k.a)の性能向上がある。
スピードアップ)。
本稿では、A3CアルゴリズムをTD(0)で修正し、A3C-TD(0)と呼ばれ、証明可能な収束を保証する。
TD更新に対する線形値関数近似により、A3C-TD(0)の収束は両方のi.d.の下で確立される。
そしてマルコフのサンプリング。
i.i.d.
サンプリングすると、A3C-TD(0)は、労働者あたり$\mathcal{O}(\epsilon^{-2.5}/N)$のサンプル複雑さを取得し、$\epsilon$精度を達成する。
2時間スケールのACに対して$\mathcal{O}(\epsilon^{-2.5})$の最もよく知られたサンプル複雑性と比較すると、A3C-TD(0) は、ACアルゴリズムの並列性と非同期性の利点を理論的に初めて正当化する \emph{linear speedup} を達成する。
合成インスタンスとOpenAI Gym環境に関する数値実験を行い,我々の理論解析を検証した。
関連論文リスト
- Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - Convergence Analysis of Decentralized ASGD [1.8710230264817358]
本稿では,ノード間の部分同期や制限的ネットワークトポロジを必要としない分散非同期SGD(DASGD)に対する新しい収束速度解析法を提案する。
我々の収束証明は、固定段数と任意の非滑らかで同質でL字型の目的函数を仮定する。
論文 参考訳（メタデータ） (2023-09-07T14:50:31Z) - Towards Understanding the Generalizability of Delayed Stochastic
Gradient Descent [63.43247232708004]
非同期で実行される勾配降下は、大規模機械学習モデルのトレーニングにおいて重要な役割を果たす。
既存の一般化誤差境界は悲観的であり、非同期遅延と一般化の相関を明らかにすることはできない。
我々の理論的結果は、非同期遅延は遅延SGDアルゴリズムの一般化誤差を低減することを示唆している。
論文 参考訳（メタデータ） (2023-08-18T10:00:27Z) - Efficient and Accurate Optimal Transport with Mirror Descent and Conjugate Gradients [13.848861021326755]
ミラーDescent Optimal Transport (MDOT) は、離散最適輸送(OT)問題を高精度に解くための新しい方法である。
MDOT は既存の OT ソルバの代表的な集合よりもはるかに高速で高精度で実現可能な解が得られることを示す。
論文 参考訳（メタデータ） (2023-07-17T14:09:43Z) - SYNTHESIS: A Semi-Asynchronous Path-Integrated Stochastic Gradient
Method for Distributed Learning in Computing Clusters [7.968142741470549]
ulstochastic gradulient ulsearchは、同期および非同期分散学習アルゴリズムの制限を克服するために開発された。
algnameアルゴリズムは(O(sqrtNepsilon-2(Delta+1) d+N))と(O(sqrtNepsilon-2(+1) d+N))を持つ
(エプシロン)分散共有メモリアーキテクチャにおける非デルタ学習の定常点
論文 参考訳（メタデータ） (2022-08-17T17:42:33Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - Finite-Time Analysis of Fully Decentralized Single-Timescale
Actor-Critic [4.94128206910124]
本稿では,アクタ,批評家,グローバル報酬推定器を交互に更新する,完全に分散化されたアクタ・クリティカル(AC)アルゴリズムを提案する。
このアルゴリズムは,Markovian サンプリングにおいて $tildemathcalO(epsilon-2)$ のサンプル複雑性を持つことを示す。
また、我々のアルゴリズムのローカルアクションプライバシ保護バージョンとその分析も提供する。
論文 参考訳（メタデータ） (2022-06-12T13:14:14Z) - 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) - Accelerating Feedforward Computation via Parallel Nonlinear Equation
Solving [106.63673243937492]
ニューラルネットワークの評価や自己回帰モデルからのサンプリングなどのフィードフォワード計算は、機械学習においてユビキタスである。
本稿では,非線形方程式の解法としてフィードフォワード計算の課題を定式化し,ジャコビ・ガウス・シーデル固定点法とハイブリッド法を用いて解を求める。
提案手法は, 並列化可能な繰り返し回数の削減(あるいは等値化)により, 元のフィードフォワード計算と全く同じ値が与えられることを保証し, 十分な並列化計算能力を付与する。
論文 参考訳（メタデータ） (2020-02-10T10:11:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。