論文の概要: Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with
Near-Optimal Sample Complexity and Communication Complexity
- arxiv url: http://arxiv.org/abs/2103.13147v1
- Date: Wed, 24 Mar 2021 12:48:08 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-25 13:45:26.695637
- Title: Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with
Near-Optimal Sample Complexity and Communication Complexity
- Title（参考訳）: マルチエージェントオフポリティTD学習:準最適サンプル複雑度と通信複雑度を用いた有限時間解析
- Authors: Ziyi Chen, Yi Zhou, Rongrong Chen
- Abstract要約: マルチエージェントオフポリシーTD学習のための2つの分散型TD補正(TDC)アルゴリズムを開発しています。
提案アルゴリズムは,エージェントの行動,ポリシー,報酬の完全なプライバシを保持し,サンプリングのばらつきと通信頻度を低減するためにミニバッチサンプリングを採用する。
- 参考スコア（独自算出の注目度）: 13.100926925535578
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The finite-time convergence of off-policy TD learning has been
comprehensively studied recently. However, such a type of convergence has not
been well established for off-policy TD learning in the multi-agent setting,
which covers broader applications and is fundamentally more challenging. This
work develops two decentralized TD with correction (TDC) algorithms for
multi-agent off-policy TD learning under Markovian sampling. In particular, our
algorithms preserve full privacy of the actions, policies and rewards of the
agents, and adopt mini-batch sampling to reduce the sampling variance and
communication frequency. Under Markovian sampling and linear function
approximation, we proved that the finite-time sample complexity of both
algorithms for achieving an $\epsilon$-accurate solution is in the order of
$\mathcal{O}(\epsilon^{-1}\ln \epsilon^{-1})$, matching the near-optimal sample
complexity of centralized TD(0) and TDC. Importantly, the communication
complexity of our algorithms is in the order of $\mathcal{O}(\ln
\epsilon^{-1})$, which is significantly lower than the communication complexity
$\mathcal{O}(\epsilon^{-1}\ln \epsilon^{-1})$ of the existing decentralized
TD(0). Experiments corroborate our theoretical findings.
- Abstract（参考訳）: オフポリシーtd学習の有限時間収束は,近年,包括的に研究されている。
しかし、このような収束は、より広範なアプリケーションをカバーするマルチエージェント環境での非政治的なTD学習には十分に確立されていない。
本研究はマルコフアンサンプリング下でのマルチエージェントオフポリシーTD学習のための修正付きTDCアルゴリズムを2つの分散TDで開発する。
特に,本アルゴリズムはエージェントの行動,ポリシー,報酬の完全なプライバシを保ち,サンプリングのばらつきと通信頻度を低減するためにミニバッチサンプリングを採用する。
マルコフのサンプリングと線形関数近似の下で、$\epsilon$-accurate 解を達成するための両方のアルゴリズムの有限時間サンプル複雑性は$\mathcal{o}(\epsilon^{-1}\ln \epsilon^{-1})$ の順であり、集中型td(0) と tdc の最適に近いサンプル複雑性と一致することを証明した。
重要なことに、アルゴリズムの通信複雑性は$\mathcal{o}(\ln \epsilon^{-1})$の順であり、既存の分散td(0)の通信複雑性$\mathcal{o}(\epsilon^{-1}\ln \epsilon^{-1})$よりもかなり低い。
実験は理論的な結果を裏付ける。
関連論文リスト
- Fully First-Order Methods for Decentralized Bilevel Optimization [17.20330936572045]
本稿では,エージェントが隣人とのみ通信する分散二段階最適化(DSBO)に焦点を当てる。
本稿では,既存の作品に広く採用されている2次オラクルよりもはるかに安価な1次オラクルのみを必要とする新しいアルゴリズムである,分散グラディエントDescent and Ascent with Gradient Tracking (DSGDA-GT)を提案する。
論文 参考訳（メタデータ） (2024-10-25T06:11:43Z) - 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) - PRECISION: Decentralized Constrained Min-Max Learning with Low
Communication and Sample Complexities [25.153506493249854]
min-max最適化問題に対する適応型マルチエージェント学習手法を提案する。
また,反復回数を削減できるPrecisionというアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-03-05T00:26:10Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Finite-Time Analysis of Fully Decentralized Single-Timescale
Actor-Critic [4.94128206910124]
本稿では,アクタ,批評家,グローバル報酬推定器を交互に更新する,完全に分散化されたアクタ・クリティカル(AC)アルゴリズムを提案する。
このアルゴリズムは,Markovian サンプリングにおいて $tildemathcalO(epsilon-2)$ のサンプル複雑性を持つことを示す。
また、我々のアルゴリズムのローカルアクションプライバシ保護バージョンとその分析も提供する。
論文 参考訳（メタデータ） (2022-06-12T13:14:14Z) - 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) - Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence
Analysis [27.679514676804057]
オフ・ポリシー・セッティングにおける2つの時間スケールTDCアルゴリズムの分散化手法を開発した。
実験により,提案した分散還元型TDCは,従来のTDCと分散還元型TDよりも収束誤差が小さいことを示した。
論文 参考訳（メタデータ） (2020-10-26T01:33:05Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。