論文の概要: Finite-Time Analysis of Fully Decentralized Single-Timescale
Actor-Critic
- arxiv url: http://arxiv.org/abs/2206.05733v1
- Date: Sun, 12 Jun 2022 13:14:14 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-15 08:07:50.618632
- Title: Finite-Time Analysis of Fully Decentralized Single-Timescale
Actor-Critic
- Title（参考訳）: 完全分散型シングルタイムスケールアクタ臨界の有限時間解析
- Authors: Qijun Luo, Xiao Li
- Abstract要約: 本稿では,アクタ,批評家,グローバル報酬推定器を交互に更新する,完全に分散化されたアクタ・クリティカル(AC)アルゴリズムを提案する。
このアルゴリズムは,Markovian サンプリングにおいて $tildemathcalO(epsilon-2)$ のサンプル複雑性を持つことを示す。
また、我々のアルゴリズムのローカルアクションプライバシ保護バージョンとその分析も提供する。
- 参考スコア（独自算出の注目度）: 4.94128206910124
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Decentralized Actor-Critic (AC) algorithms have been widely utilized for
multi-agent reinforcement learning (MARL) and have achieved remarkable success.
Apart from its empirical success, the theoretical convergence property of
decentralized AC algorithms is largely unexplored. The existing finite-time
convergence results are derived based on either double-loop update or
two-timescale step sizes rule, which is not often adopted in real
implementation. In this work, we introduce a fully decentralized AC algorithm,
where actor, critic, and global reward estimator are updated in an alternating
manner with step sizes being of the same order, namely, we adopt the
\emph{single-timescale} update. Theoretically, using linear approximation for
value and reward estimation, we show that our algorithm has sample complexity
of $\tilde{\mathcal{O}}(\epsilon^{-2})$ under Markovian sampling, which matches
the optimal complexity with double-loop implementation (here,
$\tilde{\mathcal{O}}$ hides a log term). The sample complexity can be improved
to ${\mathcal{O}}(\epsilon^{-2})$ under the i.i.d. sampling scheme. The central
to establishing our complexity results is \emph{the hidden smoothness of the
optimal critic variable} we revealed. We also provide a local action
privacy-preserving version of our algorithm and its analysis. Finally, we
conduct experiments to show the superiority of our algorithm over the existing
decentralized AC algorithms.
- Abstract（参考訳）: 分散Actor-Critic (AC) アルゴリズムはマルチエージェント強化学習 (MARL) に広く利用されており、大きな成功を収めている。
実験的な成功とは別に、分散化ACアルゴリズムの理論的収束性はほとんど未解明である。
既存の有限時間収束結果は、実実装では採用されない二重ループ更新または2時間ステップサイズルールに基づいて導出される。
本稿では,アクタ,批評家,グローバル報酬推定器を,ステップサイズを同じ順序で交互に更新する,完全に分散化されたACアルゴリズムを提案する。
理論的には、値と報酬の推定に線形近似を用いると、このアルゴリズムはマルコビアンサンプリングの下でのサンプル複雑性が$\tilde{\mathcal{O}}(\epsilon^{-2})$であることを示し、これは二重ループ実装の最適複雑性と一致する(ここでは$\tilde{\mathcal{O}}$がログ項を隠す)。
サンプルの複雑さは、i.i.d.サンプリングスキームの下で${\mathcal{o}}(\epsilon^{-2})$に改善できる。
複雑性結果の確立の中心は、我々が明らかにした最適批評家変数の隠された滑らかさである。
また、我々のアルゴリズムのローカルアクションプライバシ保護バージョンとその分析も提供する。
最後に,既存の分散交流アルゴリズムよりもアルゴリズムの優越性を示す実験を行った。
関連論文リスト
- Improved Sample Complexity for Global Convergence of Actor-Critic Algorithms [49.19842488693726]
我々は,O(epsilon-3)$のサンプル複雑性を大幅に改善したアクター・クリティック・アルゴリズムのグローバル収束を確立した。
我々の発見は、一定のステップサイズに依存する多くのアルゴリズムに対する理論的支援を提供する。
論文 参考訳（メタデータ） (2024-10-11T14:46:29Z) - Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic
Approximation with Markovian Noise [9.82187447690297]
マルコフ雑音を伴う線形2時間スケール近似 (SA) の反復に対して, 厳密な収束を特徴付ける。
この結果は,Polyak平均化を用いたTD学習,GTD,GTD2など,様々なRLアルゴリズムの収束挙動の確立に応用できる。
論文 参考訳（メタデータ） (2023-12-31T01:30:14Z) - Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
線形マルコフ決定過程(MDP)を学習するための新たな報酬なしアルゴリズムを提案する。
我々のアルゴリズムの核心は、探索駆動の擬似回帰を用いた不確実性重み付き値目標回帰である。
我々のアルゴリズムは$tilde O(d2varepsilon-2)$ episodesを探索するだけで、$varepsilon$-optimal policyを見つけることができる。
論文 参考訳（メタデータ） (2023-03-17T17:53:28Z) - A One-Sample Decentralized Proximal Algorithm for Non-Convex Stochastic
Composite Optimization [10.762749887051546]
本稿では,Proxcal$DASA-GTとProxcal$DASA-Aの2時間スケールアルゴリズムを提案する。
以前の作業とは異なり、我々のアルゴリズムは、大きなバッチサイズ、より複雑な単位演算、より強い仮定を必要とせずに、同等の複雑さを達成する。
論文 参考訳（メタデータ） (2023-02-20T05:16:18Z) - Sample and Communication-Efficient Decentralized Actor-Critic Algorithms
with Finite-Time Analysis [27.21581944906418]
Actor-critic (AC)アルゴリズムは分散マルチエージェントシステムで広く採用されている。
我々は、プライベートでサンプルと通信効率のよい2つの分散ACと自然交流(NAC)アルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-09-08T15:02:21Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - 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) - Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms [58.57004511121862]
本稿では, マルコフサンプリングにおけるACおよびNACの収束速度とサンプリング複雑性を特徴付ける。
本稿では,ACとNACがPGおよびNPGに対して,批判の組み合わさりにより,無限の地平線下での順に性能改善を実現していることを示す。
論文 参考訳（メタデータ） (2020-04-27T17:11:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。