論文の概要: On the Convergence of Alternating Regret Matching Algorithms

• arxiv url: http://arxiv.org/abs/2611.02521v1
• Date: Mon, 02 Nov 2026 04:49:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-11 20:47:09.052194
• Title: On the Convergence of Alternating Regret Matching Algorithms
• Title（参考訳）: 交代レギュレットマッチングアルゴリズムの収束性について
• Abstract要約: 後悔の一致した家族の中での交替は、ゼロサムゲームにおける実践的問題解決の中心的な要素であった。 我々のフレームワークは、導入したRVU特性の交互に類似することに集中しており、これは最適な$T-1$平均点収束を得るために使用される。 15のゲームベンチマークの実験では、半予測機構の強い理論的性質が強力な実用性能をもたらすことが示されている。
• 参考スコア（独自算出の注目度）: 58.07133626484591
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Alternating updates, that is, where each player is updated in turn, tend to typically perform better in regret matching algorithms than simultaneous updates. Alternation within the regret matching family has long been a central ingredient of practical solvers for zero-sum games. Yet our theoretical understanding is lagging behind. In this paper, we address this gap by developing a systematic way of analyzing such algorithms. Our framework centers on an alternating analog of the RVU property that we introduce, which we use to obtain the optimal $T^{-1}$ average-iterate convergence within this family. In particular, we establish this for two simple variants of predictive regret matching$^+$: i) increasing-regret predictive regret matching$^+$ and ii) half-prediction regret matching$^+$. Interestingly, we find that half prediction is the unique prediction multiplier that satisfies our alternating RVU property, giving it a strong theoretical justification. Going beyond average-iterate convergence, we refine our framework to obtain $T^{-1/2}$ best-iterate convergence and further establish convergence of their strategy profiles to a single Nash equilibrium, without assuming equilibrium uniqueness. We go on to establish separations between alternating and simultaneous updates, including a game in which half-prediction regret matching$^+$ converges under alternating updates but fails to converge in terms of the last iterate under simultaneous updates. This provides theoretical support for the empirical observation that alternation can stabilize learning dynamics. Finally, experiments on 15 game benchmarks demonstrate that the strong theoretical properties of the half-prediction mechanism translate to strong practical performance, being on par with state-of-the-art solvers.
• Abstract（参考訳）: 更新の交替、つまり各プレイヤーが順番に更新される場合、通常、同時更新よりも後悔のマッチングアルゴリズムの方がパフォーマンスが良くなる。 後悔の一致した家族の中での交替は、ゼロサムゲームにおける実践的問題解決の中心的な要素であった。 しかし、我々の理論的理解は遅れを取っている。 本稿では,このようなアルゴリズムを体系的に解析する方法を開発することで,このギャップに対処する。 我々のフレームワークは、導入したRVU特性の交互に類似することに集中しており、このファミリー内での最適な$T^{-1}$平均点収束を得るのに使用される。 特に、予測的後悔マッチングの2つの単純な変種について、これを確立している。 一 対価======================================================================= 二 半減期後悔の対価^+$ 興味深いことに、半予測は我々の交互RVU特性を満たすユニークな予測乗算であり、強い理論的正当化を与える。 平均的点収束を超えて、我々の枠組みを洗練し、平衡一意性を仮定することなく、その戦略プロファイルの1つのナッシュ平衡への収束を確立する。 繰り返し更新と同時更新の分離が確立され、半予測ミスマッチ$^+$が交互更新では収束するが、同時更新では最後の繰り返しで収束しないゲームを含む。 これは、交互化が学習力学を安定化させるという経験的観察に対する理論的支援を提供する。 最後に、15のゲームベンチマークの実験では、半予測機構の強い理論的性質が、最先端の解法と同等の強い実用性能に変換されることを示した。

関連論文リスト

• IR-PRM+ with Previous-Utility Prediction: Constant Regret and Best-Iterate Convergence [2.09124077404059]
  最近の研究でIREG-PRM+が導入された。 両方の設定をカバーする新しいアプローチを導入します。 有限2プレーヤゼロサム行列ゲームにおけるIR-PRM+の同時および交互化のために、事前効用予測は定数と収束率の保証を回復する。
  論文  参考訳（メタデータ） (2026-10-13T18:10:11Z)
• The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback [46.50566806285207]
  ゼロサム行列ゲームにおいて繰り返しプレイやバンディットフィードバックで学習する問題について検討する。 プレイヤー間の通信なしに、最終項目のナッシュ均衡への収束を保証するアンカップリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-04-17T14:17:09Z)
• Convergence of Regret Matching in Potential Games and Constrained Optimization [85.55969013318627]
  RM$+$の交互収束は、$O_epsilon (1/epsilon4)$の後に$Epsilon$-KKT点に収束し、それが音で高速な一階数であることを示す。 我々の下界は、ポテンシャルゲームにおける粗相関平衡への収束が、ナッシュ平衡への収束よりも指数関数的に速いことを示している。
  論文  参考訳（メタデータ） (2025-10-20T00:45:47Z)
• 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)
• 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)
• Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games [71.73971094342349]
  本稿では,Regret$+$ (RM$+$) に基づく2プレーヤゼロサムゲーム解決アルゴリズムの終点収束特性について検討する。 我々の分析は、アルゴリズムの極限点の幾何学的構造を新たに解析し、最終点収束に関する文献の大半から大きく離れていることを示す。
  論文  参考訳（メタデータ） (2023-11-01T17:34:58Z)

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

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