論文の概要: Efficient Last-Iterate Convergence in Regret Minimization via Adaptive Reward Transformation

• arxiv url: http://arxiv.org/abs/2509.13653v1
• Date: Wed, 17 Sep 2025 02:58:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-18 18:41:50.700616
• Title: Efficient Last-Iterate Convergence in Regret Minimization via Adaptive Reward Transformation
• Title（参考訳）: アダプティブ・リワード変換によるレギュレット最小化におけるLast-Iterateの効率的な収束
• Authors: Hang Ren, Yulin Wu, Shuhan Qi, Jiajia Zhang, Xiaozhen Sun, Tianzi Ma, Xuan Wang,
• Abstract要約: Reward Transformationフレームワークは、最後の収束を達成するために、後悔の最小化のために導入された。 本稿では,これらの問題に対処し,理論的保証と実用性能の整合性を確保するための適応手法を提案する。 我々の手法は収束を著しく加速し、最先端のアルゴリズムより優れている。
• 参考スコア（独自算出の注目度）: 12.18106607619171
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Regret minimization is a powerful method for finding Nash equilibria in Normal-Form Games (NFGs) and Extensive-Form Games (EFGs), but it typically guarantees convergence only for the average strategy. However, computing the average strategy requires significant computational resources or introduces additional errors, limiting its practical applicability. The Reward Transformation (RT) framework was introduced to regret minimization to achieve last-iterate convergence through reward function regularization. However, it faces practical challenges: its performance is highly sensitive to manually tuned parameters, which often deviate from theoretical convergence conditions, leading to slow convergence, oscillations, or stagnation in local optima. Inspired by previous work, we propose an adaptive technique to address these issues, ensuring better consistency between theoretical guarantees and practical performance for RT Regret Matching (RTRM), RT Counterfactual Regret Minimization (RTCFR), and their variants in solving NFGs and EFGs more effectively. Our adaptive methods dynamically adjust parameters, balancing exploration and exploitation while improving regret accumulation, ultimately enhancing asymptotic last-iterate convergence and achieving linear convergence. Experimental results demonstrate that our methods significantly accelerate convergence, outperforming state-of-the-art algorithms.
• Abstract（参考訳）: レグレト最小化は、通常型ゲーム(NFG)と拡張型ゲーム(EFG)におけるナッシュ均衡を見つける強力な方法であるが、通常は平均的な戦略に対してのみ収束を保証する。 しかし、平均的な戦略を計算するには、かなりの計算資源を必要とするか、追加のエラーが発生するため、実用性は制限される。 Reward Transformation (RT) フレームワークは、報酬関数の正則化を通じて最終点収束を達成するために、後悔の最小化のために導入された。 しかし、その性能は手動で調整されたパラメータに非常に敏感であり、しばしば理論的な収束条件から逸脱し、局所的なオプティマにおける緩やかな収束、発振、停滞につながる。 RTレギュレットマッチング(RTRM)、RT対実レギュレット最小化(RTCFR)、およびNFGとEFGの解法におけるそれらの変種について、理論的保証と実用性能の整合性を確保するための適応的手法を提案する。 我々の適応的手法はパラメータを動的に調整し、探索と利用のバランスを保ちながら、後悔の蓄積を改善し、最終的に漸近的最終点収束を高め、線形収束を達成する。 実験の結果,提案手法は収束を著しく加速し,最先端のアルゴリズムよりも優れていた。

関連論文リスト

• Overcoming the Loss Conditioning Bottleneck in Optimization-Based PDE Solvers: A Novel Well-Conditioned Loss Function [1.6135205846394396]
  近年,スカラー損失関数を最小化するPDEソルバが注目されている。 このような手法は古典的反復解法よりもはるかにゆっくりと収束し、一般に非効率的とみなされる。 この研究は理論的な洞察を与え、平均二乗誤差(MSE)損失の使用に非効率性をもたらす。 重みパラメータをチューニングすることにより、制限ケースでのMSE損失を低減しつつ、元のシステムとその正規方程式の間の条件数を柔軟に変調する。
  論文  参考訳（メタデータ） (2025-07-24T10:17:02Z)
• Efficient Differentiable Approximation of Generalized Low-rank Regularization [64.73416824444328]
  低ランク正規化(LRR)は様々な機械学習タスクに広く応用されている。 本稿では,LRRの効率的な微分可能近似を提案する。
  論文  参考訳（メタデータ） (2025-05-21T11:49:17Z)
• Achieving Constraints in Neural Networks: A Stochastic Augmented Lagrangian Approach [49.1574468325115]
  DNN(Deep Neural Networks)の正規化は、一般化性の向上とオーバーフィッティングの防止に不可欠である。 制約付き最適化問題としてトレーニングプロセスのフレーミングによるDNN正規化に対する新しいアプローチを提案する。 我々はAugmented Lagrangian (SAL) 法を用いて、より柔軟で効率的な正規化機構を実現する。
  論文  参考訳（メタデータ） (2023-10-25T13:55:35Z)
• Efficient Last-iterate Convergence Algorithms in Solving Games [29.25745562794961]
  近年の研究では、元のEFGのNEを、(摂動された)正規化されたEFGの列のNEを学ぶように再構成している。 本稿では,古典的パラメータフリーなRMベースのCFRアルゴリズムであるCFR$+$が,摂動正規化EFGのNEを学習する際の最終点収束を実現することを証明する。
  論文  参考訳（メタデータ） (2023-08-22T07:59:49Z)
• The Power of Regularization in Solving Extensive-Form Games [28.043425786728157]
  より弱い仮定かより強い収束保証を条件として,ゲームのファンクションペイオフの正規化に基づく,一連の新しいアルゴリズムを提案する。 我々の知る限り、これらは、非摂動EFGのNEを求める際に、最先端の平均収束率と整合しながら、CFR型アルゴリズムの最終的な収束結果を構成する。
  論文  参考訳（メタデータ） (2022-06-19T22:10:38Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。 我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。 有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
  論文  参考訳（メタデータ） (2020-08-28T14:46:56Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。 ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
  論文  参考訳（メタデータ） (2020-07-02T16:02:02Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  適応性は現代最適化理論において重要であるが、研究されていない性質である。 提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
  論文  参考訳（メタデータ） (2020-02-13T05:42:27Z)

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

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