論文の概要: Last-iterate Convergence Separation between Extra-gradient and Optimism in Constrained Periodic Games

• arxiv url: http://arxiv.org/abs/2406.10605v1
• Date: Sat, 15 Jun 2024 11:50:36 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-18 23:33:44.163486
• Title: Last-iterate Convergence Separation between Extra-gradient and Optimism in Constrained Periodic Games
• Title（参考訳）: 制限された周期ゲームにおける外段階と最適点のLast-iterate Convergence分離
• Authors: Yi Feng, Ping Li, Ioannis Panageas, Xiao Wang,
• Abstract要約: 2人プレイのゼロサムゲームにおける学習アルゴリズムの終局的動作について、広範囲に研究されている。 既存の結果の多くは、ゲームが時間に依存しないという仮定の下でこれらの特性を確立する。 本稿では,制約付き周期ゲームにおける楽観的および外段階的手法の終局的挙動について検討する。
• 参考スコア（独自算出の注目度）: 31.989723099872638
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Last-iterate behaviors of learning algorithms in repeated two-player zero-sum games have been extensively studied due to their wide applications in machine learning and related tasks. Typical algorithms that exhibit the last-iterate convergence property include optimistic and extra-gradient methods. However, most existing results establish these properties under the assumption that the game is time-independent. Recently, (Feng et al, 2023) studied the last-iterate behaviors of optimistic and extra-gradient methods in games with a time-varying payoff matrix, and proved that in an unconstrained periodic game, extra-gradient method converges to the equilibrium while optimistic method diverges. This finding challenges the conventional wisdom that these two methods are expected to behave similarly as they do in time-independent games. However, compared to unconstrained games, games with constrains are more common both in practical and theoretical studies. In this paper, we investigate the last-iterate behaviors of optimistic and extra-gradient methods in the constrained periodic games, demonstrating that similar separation results for last-iterate convergence also hold in this setting.
• Abstract（参考訳）: 繰り返し2人プレイのゼロサムゲームにおける学習アルゴリズムの最終的な動作は、機械学習や関連するタスクに広く応用されているため、広く研究されている。 最後の点収束性を示す典型的なアルゴリズムには、楽観的および外段階的な方法がある。 しかし、既存の結果のほとんどは、ゲームが時間に依存しないという仮定の下でこれらの性質を確立する。 近年, (Feng et al, 2023) は, 時間的変化のあるペイオフ行列を持つゲームにおいて, 楽観的および外段階的手法の最後の定位挙動を研究し, 楽観的手法が分岐しながら, 非制約周期ゲームにおいて, 外段階的手法が平衡に収束することを証明した。 この発見は、これらの2つの方法が時間に依存しないゲームと同じように振る舞うことが期待されているという従来の知恵に挑戦する。 しかし、制約のないゲームと比較して、現実的および理論的研究において制約のあるゲームの方が一般的である。 本稿では,制約付き周期ゲームにおける楽観的および非定常的手法の終局的挙動について検討し,この設定において最終段階収束に対する同様の分離結果が成立することを示した。

関連論文リスト

• The equivalence of dynamic and strategic stability under regularized learning in games [33.74394172275373]
  有限ゲームにおける正規化学習の長時間動作について検討する。 戦略的安定性と動的安定性の等価性を得る。 エントロピー正則化に基づく手法は幾何速度で収束することを示す。
  論文  参考訳（メタデータ） (2023-11-04T14:07:33Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。 我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。 また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
  論文  参考訳（メタデータ） (2023-01-26T17:25:45Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。 ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。 本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
  論文  参考訳（メタデータ） (2022-11-29T05:16:41Z)
• 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)
• No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
  固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。 提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。 本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
  論文  参考訳（メタデータ） (2022-01-30T06:10:04Z)
• Online Learning in Periodic Zero-Sum Games [27.510231246176033]
  これらの力学系の複雑で非自律的な性質にもかかわらず、ポアンカーの再発は確実に一般化することを示す。
  論文  参考訳（メタデータ） (2021-11-05T10:36:16Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  逐次ゲームにおける楽観的アルゴリズムの最後の点収束について検討する。 これらのアルゴリズムはいずれも最終点収束を楽しみ、そのいくつかは指数関数的に高速に収束する。
  論文  参考訳（メタデータ） (2021-06-27T22:02:26Z)
• Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games [116.0771177871705]
  我々は,$lambda$-cocoerciveゲーム上での連立OGD学習における有限時間最終点収束率を特徴付ける。 新たなダブルストッピング時間法により, この適応アルゴリズムは, 非適応的手法と同じ有限時間終点収束率が得られることを示す。
  論文  参考訳（メタデータ） (2020-02-23T01:46:34Z)

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

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