論文の概要: From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications

• arxiv url: http://arxiv.org/abs/2506.03464v1
• Date: Wed, 04 Jun 2025 00:24:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-05 21:20:14.093137
• Title: From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications
• Title（参考訳）: ゲームにおける平均イテレートから最終イテレート収束:削減とその応用
• Authors: Yang Cai, Haipeng Luo, Chen-Yu Wei, Weiqiang Zheng,
• Abstract要約: 大規模なゲームでは、非結合学習ダイナミクスの平均的な繰り返しを新しい非結合学習ダイナミクスの最後の繰り返しに変換する単純なブラックボックス還元が存在することを示す。 2人のプレイヤーのゼロサム正規形式ゲームにおける非結合学習ダイナミクスに対する最先端最後の収束率を得る。
• 参考スコア（独自算出の注目度）: 44.95137108337898
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The convergence of online learning algorithms in games under self-play is a fundamental question in game theory and machine learning. Among various notions of convergence, last-iterate convergence is particularly desirable, as it reflects the actual decisions made by the learners and captures the day-to-day behavior of the learning dynamics. While many algorithms are known to converge in the average-iterate, achieving last-iterate convergence typically requires considerably more effort in both the design and the analysis of the algorithm. Somewhat surprisingly, we show in this paper that for a large family of games, there exists a simple black-box reduction that transforms the average iterates of an uncoupled learning dynamics into the last iterates of a new uncoupled learning dynamics, thus also providing a reduction from last-iterate convergence to average-iterate convergence. Our reduction applies to games where each player's utility is linear in both their own strategy and the joint strategy of all opponents. This family includes two-player bimatrix games and generalizations such as multi-player polymatrix games. By applying our reduction to the Optimistic Multiplicative Weights Update algorithm, we obtain new state-of-the-art last-iterate convergence rates for uncoupled learning dynamics in two-player zero-sum normal-form games: (1) an $O(\frac{\log d}{T})$ last-iterate convergence rate under gradient feedback, representing an exponential improvement in the dependence on the dimension $d$ (i.e., the maximum number of actions available to either player); and (2) an $\widetilde{O}(d^{\frac{1}{5}} T^{-\frac{1}{5}})$ last-iterate convergence rate under bandit feedback, improving upon the previous best rates of $\widetilde{O}(\sqrt{d} T^{-\frac{1}{8}})$ and $\widetilde{O}(\sqrt{d} T^{-\frac{1}{6}})$.
• Abstract（参考訳）: セルフプレイゲームにおけるオンライン学習アルゴリズムの収束は、ゲーム理論と機械学習の基本的な問題である。 収束の様々な概念の中で、学習者による実際の決定を反映し、学習ダイナミクスの日々の振る舞いを捉えているため、最終段階の収束が特に望ましい。 多くのアルゴリズムは平均的イテレートに収束することが知られているが、最終イテレート収束を達成するには、アルゴリズムの設計と解析の両方にかなり多くの労力を要するのが普通である。 意外なことに、この論文では、多くのゲームに対して、非結合学習のダイナミクスの平均的な繰り返しを新しい非結合学習のダイナミクスの最後の繰り返しに変換する単純なブラックボックス還元が存在することを示し、また、最終要素収束から平均要素収束へ還元する。 我々の削減は、各プレイヤーの効用が自身の戦略と全ての対戦者の共同戦略の両方において線形であるゲームに適用される。 このファミリーには、2人のプレイヤーのビマトリクスゲームと、マルチプレイヤーのポリマトリクスゲームのような一般化が含まれている。 Optimistic Multiplicative Weights Updateアルゴリズムに適用することにより、(1)$O(\frac{\log d}{T})$ last-iterate convergence rateを勾配フィードバックの下で指数関数的に改善し、次元$d$(つまり、どちらのプレイヤーにも利用可能なアクションの最大数)と(2)$\widetilde{O}(d^{\frac{1}{5}} T^{-\frac{1}{5}})$ last-iterate convergence rateをバンドレートフィードバックで改善し、以前の最高値である$\widetilde{O}(d^{\frac{1}{5}}T^{-\frac{1}{5}})で改善する。

関連論文リスト

• On Separation Between Best-Iterate, Random-Iterate, and Last-Iterate Convergence of Learning in Games [71.73971094342349]
  ゲームにおける学習力学の非エルゴード収束は、理論と実践の両方において重要であるため、広く研究されている。 近年の研究では、最適乗算重み更新を含む学習力学の幅広いクラスが、任意に遅い最終項目収束を示すことが示されている。 OMWUは、同じクラスのゲームにおいて、その遅い最終点収束とは対照的に、$O(T-1/6)$est-iterate convergence rateを達成することを示す。
  論文  参考訳（メタデータ） (2025-03-04T17:49:24Z)
• Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms [71.73971094342349]
  オンライン学習によるセルフプレイは、大規模な2人プレイのゼロサムゲームを解くための重要な方法の1つだ。 我々は,OMWUが支払行列のサイズに対数依存するなど,いくつかの利点があることを示した。 我々は、過去のことをすぐに忘れない幅広い種類のアルゴリズムが、すべて同じ問題に悩まされていることを証明している。
  論文  参考訳（メタデータ） (2024-06-15T13:26:17Z)
• Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games [71.73971094342349]
  本稿では,Regret$+$ (RM$+$) に基づく2プレーヤゼロサムゲーム解決アルゴリズムの終点収束特性について検討する。 我々の分析は、アルゴリズムの極限点の幾何学的構造を新たに解析し、最終点収束に関する文献の大半から大きく離れていることを示す。
  論文  参考訳（メタデータ） (2023-11-01T17:34:58Z)

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

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