論文の概要: Fast and Furious Symmetric Learning in Zero-Sum Games: Gradient Descent as Fictitious Play

• arxiv url: http://arxiv.org/abs/2506.13086v1
• Date: Mon, 16 Jun 2025 04:07:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-17 17:28:47.48304
• Title: Fast and Furious Symmetric Learning in Zero-Sum Games: Gradient Descent as Fictitious Play
• Title（参考訳）: ゼロサムゲームにおける高速かつ虚偽の対称性学習--架空のプレーとしてのグラディエント・ダイス
• Authors: John Lazarsfeld, Georgios Piliouras, Ryann Sim, Andre Wibisono,
• Abstract要約: 本稿では,ゼロサムゲームにおける2つの非regretアルゴリズムのサブ線形後悔保証について検討する。 Fictitious Play と Online Gradient Descent は、正規化がないために不安定さと線形後悔を示す。 我々は、任意のタイブレークルールを持つ有限プレイが$O(sqrtT)$後悔していることを証明し、カルリンの有限プレイ予想が持つ新しいクラスのゲームを確立する。
• 参考スコア（独自算出の注目度）: 39.1873150563222
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper investigates the sublinear regret guarantees of two non-no-regret algorithms in zero-sum games: Fictitious Play, and Online Gradient Descent with constant stepsizes. In general adversarial online learning settings, both algorithms may exhibit instability and linear regret due to no regularization (Fictitious Play) or small amounts of regularization (Gradient Descent). However, their ability to obtain tighter regret bounds in two-player zero-sum games is less understood. In this work, we obtain strong new regret guarantees for both algorithms on a class of symmetric zero-sum games that generalize the classic three-strategy Rock-Paper-Scissors to a weighted, n-dimensional regime. Under symmetric initializations of the players' strategies, we prove that Fictitious Play with any tiebreaking rule has $O(\sqrt{T})$ regret, establishing a new class of games for which Karlin's Fictitious Play conjecture holds. Moreover, by leveraging a connection between the geometry of the iterates of Fictitious Play and Gradient Descent in the dual space of payoff vectors, we prove that Gradient Descent, for almost all symmetric initializations, obtains a similar $O(\sqrt{T})$ regret bound when its stepsize is a sufficiently large constant. For Gradient Descent, this establishes the first "fast and furious" behavior (i.e., sublinear regret without time-vanishing stepsizes) for zero-sum games larger than 2x2.
• Abstract（参考訳）: 本稿では,ゼロサムゲームにおける2つのノンレグレットアルゴリズムのサブ線形後悔保証について検討する。 一般の対向的なオンライン学習設定では、両アルゴリズムは正則化(Factitious Play)や少量の正則化(Gradient Descent)を伴わないため、不安定性と線形後悔を示す可能性がある。 しかし、2人プレイのゼロサムゲームにおいて、より厳密な後悔境界を得る能力は理解されていない。 本研究は,古典的三ストラテジーRock-Paper-Scissorsを重み付きn次元状態に一般化する対称ゼロサムゲームにおいて,両アルゴリズムの強い後悔の保証を得る。 プレイヤーの戦略の対称的初期化の下では、任意のタイブレークルールを持つ有限プレイが$O(\sqrt{T})$後悔を持つことを証明し、カーリンの有限プレイ予想が成立する新しい種類のゲームを確立する。 さらに、Factitious Play のイテレートの幾何とペイオフベクトルの双対空間におけるグラディエントDescent の接続を利用して、ほぼすべての対称初期化に対して、その階段化が十分に大きな定数であるときに同様の$O(\sqrt{T})$後悔境界が得られることを証明する。 グラディエント・Descent にとって、これは 2x2 より大きいゼロサムゲームに対する最初の「高速で激怒な」行動(すなわち、時空の段数を持たないサブ線形後悔)を確立する。

関連論文リスト

• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。 我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。 また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
  論文  参考訳（メタデータ） (2023-01-26T17:25:45Z)
• Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
  一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。 我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。 先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
  論文  参考訳（メタデータ） (2022-06-17T12:58:58Z)
• No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
  固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。 提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。 本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
  論文  参考訳（メタデータ） (2022-01-30T06:10:04Z)
• Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games [36.969021834291745]
  本稿では,仮説クラスの逐次的脂肪散乱次元の観点から,ほぼ最適誤差を導出する固有学習アルゴリズムを提案する。 この結果は、適切な学習者が準最適誤り境界を達成できるかどうかという疑問に答える。 実数値(回帰)設定では、最適誤り境界は不適切な学習者にさえ知られていなかった。
  論文  参考訳（メタデータ） (2021-11-17T05:24:21Z)

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

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