論文の概要: 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})$よりもかなり低い。
実験は理論的な結果を裏付ける。
関連論文リスト
- Nearly Optimal Sample Complexity of Offline KL-Regularized Contextual Bandits under Single-Policy Concentrability [49.96531901205305]
我々は,オフラインの文脈的包帯に対する単一政治中心性の下でのサンプル複雑性を$tildeO(epsilon-1)$とするemphfirstアルゴリズムを提案する。
我々の証明は、KL正則化の強い凸性と、真の報酬と悲観的推定子のギャップの条件的非負性を利用する。
我々は,このアルゴリズムを文脈的デュエル帯域に拡張し,ほぼ最適なサンプル複雑性を実現する。
論文 参考訳（メタデータ） (2025-02-09T22:14:45Z) - Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。