論文の概要: The Power of Regularization in Solving Extensive-Form Games

• arxiv url: http://arxiv.org/abs/2206.09495v3
• Date: Wed, 09 Jul 2025 03:58:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-11 18:48:43.504303
• Title: The Power of Regularization in Solving Extensive-Form Games
• Title（参考訳）: 総合型ゲームにおける正規化の力
• Authors: Mingyang Liu, Asuman Ozdaglar, Tiancheng Yu, Kaiqing Zhang,
• Abstract要約: より弱い仮定かより強い収束保証を条件として,ゲームのファンクションペイオフの正規化に基づく,一連の新しいアルゴリズムを提案する。 我々の知る限り、これらは、非摂動EFGのNEを求める際に、最先端の平均収束率と整合しながら、CFR型アルゴリズムの最終的な収束結果を構成する。
• 参考スコア（独自算出の注目度）: 28.043425786728157
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we investigate the power of {\it regularization}, a common technique in reinforcement learning and optimization, in solving extensive-form games (EFGs). We propose a series of new algorithms based on regularizing the payoff functions of the game, and establish a set of convergence results that strictly improve over the existing ones, with either weaker assumptions or stronger convergence guarantees. In particular, we first show that dilated optimistic mirror descent (DOMD), an efficient variant of OMD for solving EFGs, with adaptive regularization can achieve a fast $\tilde O(1/T)$ {last-iterate convergence rate for the output of the algorithm} in terms of duality gap and distance to the set of Nash equilibrium (NE) without uniqueness assumption of the NE. Second, we show that regularized counterfactual regret minimization (\texttt{Reg-CFR}), with a variant of optimistic mirror descent algorithm as regret-minimizer, can achieve $O(1/T^{1/4})$ best-iterate, and $O(1/T^{3/4})$ average-iterate convergence rate for finding NE in EFGs. Finally, we show that \texttt{Reg-CFR} can achieve asymptotic last-iterate convergence, and optimal $O(1/T)$ average-iterate convergence rate, for finding the NE of perturbed EFGs, which is useful for finding approximate extensive-form perfect equilibria (EFPE). To the best of our knowledge, they constitute the first last-iterate convergence results for CFR-type algorithms, while matching the state-of-the-art average-iterate convergence rate in finding NE for non-perturbed EFGs. We also provide numerical results to corroborate the advantages of our algorithms.
• Abstract（参考訳）: 本稿では,強化学習と最適化において一般的な手法である,拡張形式ゲーム(EFG)のパワーについて検討する。 ゲームにおけるペイオフ関数の正規化に基づく新しいアルゴリズムのシリーズを提案し、より弱い仮定やより強いコンバージェンス保証を用いて、既存のアルゴリズムよりも厳密に改善する一連の収束結果を確立する。 特に、適応正則化を用いてEFGを解くためのOMDの効率的な変種である拡張楽観的ミラー降下 (DOMD) が、NEの特異性を仮定することなく、双対性ギャップとナッシュ平衡 (NE) の集合との距離で高速な$\tilde O(1/T)$ {last-iterate convergence rateを達成できることを最初に示す。 第二に、正則化された反事実的後悔最小化(\texttt{Reg-CFR})は、楽観的ミラー降下アルゴリズムの変形を最小化して、EFGにおけるNEを見つけるための平均収束率$O(1/T^{1/4})と$O(1/T^{3/4})を達成できることを示す。 最後に,<texttt{Reg-CFR} は漸近的終点収束を達成でき,O(1/T)$ average-iterate convergence rate は摂動 EFG の NE を求めるために最適であることを示す。 我々の知る限り、これらは、非摂動EFGのNEを求める際に、最先端の平均収束率と整合しながら、CFR型アルゴリズムの最終的な収束結果を構成する。 また,アルゴリズムの利点を裏付ける数値的な結果も提供する。

関連論文リスト

• 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)
• Convergence Rate Analysis of LION [54.28350823319057]
  LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。 従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
  論文  参考訳（メタデータ） (2024-11-12T11:30:53Z)
• A Fresh Look at Generalized Category Discovery through Non-negative Matrix Factorization [83.12938977698988]
  Generalized Category Discovery (GCD) は、ラベル付きベースデータを用いて、ベース画像と新規画像の両方を分類することを目的としている。 現在のアプローチでは、コサイン類似性に基づく共起行列 $barA$ の固有の最適化に不適切に対処している。 本稿では,これらの欠陥に対処するNon-Negative Generalized Category Discovery (NN-GCD) フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-10-29T07:24:11Z)
• Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods [25.831462008050387]
  グラディエント・Descent(SGD)アルゴリズムは、実際の性能が良く、理論的な理解が欠如していることから、人々の関心を喚起している。 有限収束がより広い合成最適化や非ユークリッドノルムに証明可能な拡張が可能かどうかはまだ不明である。
  論文  参考訳（メタデータ） (2023-12-13T21:41:06Z)
• 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)
• Efficient Last-iterate Convergence Algorithms in Solving Games [20.00785679098103]
  非回帰アルゴリズムは、2プレイヤゼロサム正規形式ゲーム(NFG)およびワイドフォームゲーム(EFG)におけるナッシュ均衡の学習に人気がある。 近年,MWU に対するリワード変換 (RT) フレームワークが提案されている。 RTアルゴリズムのボトルネックは凸凹最適化問題(SCCP)の解法であることを示す。
  論文  参考訳（メタデータ） (2023-08-22T07:59:49Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。 既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。 本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
  論文  参考訳（メタデータ） (2022-10-08T08:26:22Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  逐次ゲームにおける楽観的アルゴリズムの最後の点収束について検討する。 これらのアルゴリズムはいずれも最終点収束を楽しみ、そのいくつかは指数関数的に高速に収束する。
  論文  参考訳（メタデータ） (2021-06-27T22:02:26Z)
• Linear Last-iterate Convergence in Constrained Saddle-point Optimization [48.44657553192801]
  我々は、OGDA(Optimistic Gradient Descent Ascent)とOMWU(Optimistic Multiplicative Weights Update)に対する最終段階の独特さの理解を著しく拡大する。 平衡が一意である場合、線形終端収束は、値が普遍定数に設定された学習速度で達成されることを示す。 任意のポリトープ上の双線型ゲームがこの条件を満たすことを示し、OGDAは一意の平衡仮定なしで指数関数的に高速に収束することを示した。
  論文  参考訳（メタデータ） (2020-06-16T20:53:04Z)

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

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