論文の概要: Scale-Invariant Fast Convergence in Games

• arxiv url: http://arxiv.org/abs/2602.11857v1
• Date: Thu, 12 Feb 2026 11:57:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-13 21:07:25.794885
• Title: Scale-Invariant Fast Convergence in Games
• Title（参考訳）: ゲームにおけるスケール不変高速収束
• Authors: Taira Tsuchiya, Haipeng Luo, Shinji Ito,
• Abstract要約: 我々は,スケールフリーでもスケール不変でも,高速収束を実現する学習力学を開発した。 2プレーヤゼロサムゲームに対しては、$tildeO(A_mathrmdiff)$で有界な外部後悔を伴うスケールフリーかつスケール不変のダイナミクスが得られる。 マルチプレイヤーの汎用ゲームでは、過去の観測に基づいて観察された勾配をクリップする2倍のクリッピングと呼ばれる手法によって、スケールフリーの学習も可能となる。
• 参考スコア（独自算出の注目度）: 67.02769061793619
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Scale-invariance in games has recently emerged as a widely valued desirable property. Yet, almost all fast convergence guarantees in learning in games require prior knowledge of the utility scale. To address this, we develop learning dynamics that achieve fast convergence while being both scale-free, requiring no prior information about utilities, and scale-invariant, remaining unchanged under positive rescaling of utilities. For two-player zero-sum games, we obtain scale-free and scale-invariant dynamics with external regret bounded by $\tilde{O}(A_{\mathrm{diff}})$, where $A_{\mathrm{diff}}$ is the payoff range, which implies an $\tilde{O}(A_{\mathrm{diff}} / T)$ convergence rate to Nash equilibrium after $T$ rounds. For multiplayer general-sum games with $n$ players and $m$ actions, we obtain scale-free and scale-invariant dynamics with swap regret bounded by $O(U_{\mathrm{max}} \log T)$, where $U_{\mathrm{max}}$ is the range of the utilities, ignoring the dependence on the number of players and actions. This yields an $O(U_{\mathrm{max}} \log T / T)$ convergence rate to correlated equilibrium. Our learning dynamics are based on optimistic follow-the-regularized-leader with an adaptive learning rate that incorporates the squared path length of the opponents' gradient vectors, together with a new stopping-time analysis that exploits negative terms in regret bounds without scale-dependent tuning. For general-sum games, scale-free learning is enabled also by a technique called doubling clipping, which clips observed gradients based on past observations.
• Abstract（参考訳）: ゲームにおけるスケール不変性は、最近広く評価された望ましい性質として現れている。 しかし、ゲームにおける学習において、ほとんど全ての高速収束を保証するには、実用規模に関する事前の知識が必要である。 これを解決するために、我々は、実用性に関する事前情報やスケール不変性を必要とせず、実用性に対するポジティブな再スケーリングの下でも変化のない、高速収束を実現する学習力学を開発する。 2プレイヤゼロサムゲームに対しては、$\tilde{O}(A_{\mathrm{diff}})$, ここで$A_{\mathrm{diff}}$はペイオフ範囲であり、$\tilde{O}(A_{\mathrm{diff}} / T)$$T$ラウンド後のナッシュ平衡への収束率を意味する。 n$プレーヤーと$m$アクションを持つマルチプレイヤーの汎用ゲームの場合、$O(U_{\mathrm{max}} \log T)$で区切られたリフレッシュでスケールフリーでスケール不変なダイナミクスを得る。 これにより、相関平衡に対する$O(U_{\mathrm{max}} \log T / T)$収束速度が得られる。 我々の学習力学は、適応的な学習率を持つ楽観的な追従型リーダーに基づいており、これは、相手の勾配ベクトルの2乗経路長を組み込むとともに、スケール依存的なチューニングを伴わずに、後悔境界における負の項を利用する新しい停止時間解析である。 一般的なゲームの場合、スケールフリーの学習は、過去の観測に基づいて観察された勾配をクリップする2倍のクリッピングと呼ばれる手法によっても可能となる。

関連論文リスト

• Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Games [60.871651115241406]
  ゼロサムゲームにおける理論と実践の間、何十年にもわたってかなりのシャズムが一階法によって浸食されてきた。 我々は、IREG-PRM$+$と呼ぶPRM$+$の新しいスケール不変かつパラメータフリーな変種を提案する。 ベンチマークゲームでは, PRM$+$と同等でありながら, 最適収束保証を$T-1/2$, $T-1$とする。
  論文  参考訳（メタデータ） (2025-10-06T00:33:20Z)
• From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications [54.49053278073321]
  大規模なゲームでは、非結合学習ダイナミクスの平均的な繰り返しを新しい非結合学習ダイナミクスの最後の繰り返しに変換する単純なブラックボックス還元が存在することを示す。 我々の削減は、各プレイヤーの効用が自身の戦略と全ての対戦者の共同戦略の両方において線形であるゲームに適用される。
  論文  参考訳（メタデータ） (2025-06-04T00:24:14Z)
• Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback [60.610120215789976]
  純粋な戦略 ナッシュ均衡が存在するとき、$c$ は 0 となり、最適のインスタンス依存後悔境界となることを示す。 また,本アルゴリズムは最終段階の収束性も享受し,ほぼ最適サンプルを用いて純粋な戦略ナッシュ均衡を同定することができる。
  論文  参考訳（メタデータ） (2025-02-24T20:20:06Z)
• Corrupted Learning Dynamics in Games [62.73758165845971]
  すべてのプレイヤーが楽観的な追従型リーダー(OFTRL)に従うと、平衡は$O(log T)$の速さで計算できる。 本稿では,各プレイヤーが所定のアルゴリズムによって提案される戦略から逸脱する程度に依存する速度で,適応的に平衡を求める学習ダイナミクスを提案する。
  論文  参考訳（メタデータ） (2024-12-10T02:23:44Z)
• Local Convergence of Gradient Methods for Min-Max Games: Partial Curvature Generically Suffices [0.5439020425819]
  2つのプレイヤーゼロサム微分可能なゲームに対する勾配法の局所的ナッシュ平衡の収束について検討する。 偏曲のおかげで、円錐粒子法 -- 重みを最適化し、混合戦略をサポートする -- は、固定支持法よりも一般的に収束する。
  論文  参考訳（メタデータ） (2023-05-26T21:43:56Z)
• Gradient Descent-Ascent Provably Converges to Strict Local Minmax Equilibria with a Finite Timescale Separation [11.091975655053547]
  有限時間スケールの分離パラメータ $tau$ は、非プレイヤ、非コンケーブゼロサムゲームにおいて勾配降下度に比例することを示す。 タイムスケールコンピューティングがパフォーマンスに与える影響を実証的に示す。
  論文  参考訳（メタデータ） (2020-09-30T17:51:28Z)

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

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