論文の概要: Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games

• arxiv url: http://arxiv.org/abs/2002.09806v5
• Date: Sat, 17 Jul 2021 06:09:20 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-29 09:55:46.629040
• Title: Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games
• Title（参考訳）: ゲームにおけるマルチエージェント学習のための有限時間ラストイテレート収束
• Authors: Tianyi Lin, Zhengyuan Zhou, Panayotis Mertikopoulos and Michael I. Jordan
• Abstract要約: 我々は,$lambda$-cocoerciveゲーム上での連立OGD学習における有限時間最終点収束率を特徴付ける。 新たなダブルストッピング時間法により, この適応アルゴリズムは, 非適応的手法と同じ有限時間終点収束率が得られることを示す。
• 参考スコア（独自算出の注目度）: 116.0771177871705
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we consider multi-agent learning via online gradient descent in a class of games called $\lambda$-cocoercive games, a fairly broad class of games that admits many Nash equilibria and that properly includes unconstrained strongly monotone games. We characterize the finite-time last-iterate convergence rate for joint OGD learning on $\lambda$-cocoercive games; further, building on this result, we develop a fully adaptive OGD learning algorithm that does not require any knowledge of problem parameter (e.g. cocoercive constant $\lambda$) and show, via a novel double-stopping time technique, that this adaptive algorithm achieves same finite-time last-iterate convergence rate as non-adaptive counterpart. Subsequently, we extend OGD learning to the noisy gradient feedback case and establish last-iterate convergence results -- first qualitative almost sure convergence, then quantitative finite-time convergence rates -- all under non-decreasing step-sizes. To our knowledge, we provide the first set of results that fill in several gaps of the existing multi-agent online learning literature, where three aspects -- finite-time convergence rates, non-decreasing step-sizes, and fully adaptive algorithms have been unexplored before.
• Abstract（参考訳）: 本稿では,Nash平衡が多数あり,制約のない強いモノトーンゲームが適切に含まれているゲームクラスである$\lambda$-cocoerciveゲームと呼ばれるゲームクラスにおいて,オンライン勾配勾配によるマルチエージェント学習を検討する。 我々は、$\lambda$-cocoerciveゲーム上での連立OGD学習における有限時間最後の収束率を特徴付け、この結果に基づいて、問題パラメータ(例えば、cocoercive constant $\lambda$)の知識を必要としない完全に適応的なOGD学習アルゴリズムを開発し、新しいダブルストッピングタイム技術を通して、この適応アルゴリズムが非適応性ゲームと同じ有限時間最後の収束率を達成することを示す。 その後、ogd学習をノイズの勾配フィードバックケースに拡張し、最初の定性的なほぼ確実に収束し、次に定量的な有限時間収束率という最終段階の収束結果を確立する。 私たちの知る限り、我々は、既存のマルチエージェントオンライン学習文献のいくつかのギャップを埋める最初の結果を提供しています。

関連論文リスト

• Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
  オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。 本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
  論文  参考訳（メタデータ） (2023-10-21T18:38:13Z)
• Smoothing ADMM for Sparse-Penalized Quantile Regression with Non-Convex Penalties [8.294148737585543]
  本稿では,非二次絶対および非平滑収束ペナルティの存在下での凹凸および切断された量子レグレッションについて検討する。 本稿では,スパース回帰に特化してSIADと呼ばれるペナルティ乗算器が増加する新しいループADMアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-04T21:48:51Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。 我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。 また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
  論文  参考訳（メタデータ） (2023-01-26T17:25:45Z)
• Asynchronous Gradient Play in Zero-Sum Multi-agent Games [25.690033495071923]
  ゼロサムポリマトリクスゲームにおける遅延フィードバック下での非同期勾配プレイについて検討した。 我々の知る限りでは、この研究はゼロサムポリマトリクスゲームにおける非同期勾配プレイを理解することを目的とした最初のものである。
  論文  参考訳（メタデータ） (2022-11-16T15:37:23Z)
• A unified stochastic approximation framework for learning in games [82.74514886461257]
  ゲームにおける学習の長期的挙動(連続的・有限的)を解析するためのフレキシブルな近似フレームワークを開発する。 提案する分析テンプレートには,勾配に基づく手法,有限ゲームでの学習のための指数的/乗算的重み付け,楽観的および帯域的変異など,幅広い一般的な学習アルゴリズムが組み込まれている。
  論文  参考訳（メタデータ） (2022-06-08T14:30:38Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  逐次ゲームにおける楽観的アルゴリズムの最後の点収束について検討する。 これらのアルゴリズムはいずれも最終点収束を楽しみ、そのいくつかは指数関数的に高速に収束する。
  論文  参考訳（メタデータ） (2021-06-27T22:02:26Z)
• Finite-Time Analysis for Double Q-learning [50.50058000948908]
  二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。 同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
  論文  参考訳（メタデータ） (2020-09-29T18:48:21Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。