論文の概要: IR-PRM+ with Previous-Utility Prediction: Constant Regret and Best-Iterate Convergence

• arxiv url: http://arxiv.org/abs/2610.19016v1
• Date: Tue, 13 Oct 2026 18:10:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-15 21:06:15.741236
• Title: IR-PRM+ with Previous-Utility Prediction: Constant Regret and Best-Iterate Convergence
• Title（参考訳）: 既往の実用性予測を備えたIR-PRM+:定数レグレストと最良Iterate Convergence
• Abstract要約: 最近の研究でIREG-PRM+が導入された。 両方の設定をカバーする新しいアプローチを導入します。 有限2プレーヤゼロサム行列ゲームにおけるIR-PRM+の同時および交互化のために、事前効用予測は定数と収束率の保証を回復する。
• 参考スコア（独自算出の注目度）: 2.09124077404059
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Regret matching (and its variants) and counterfactual regret minimization are central algorithms in practice for normal-form and extensive-form game solving. Yet these have historically lacked the stronger theoretical convergence guarantees available to optimistic and extra-gradient methods. Recent work introduced IREG-PRM+, a regret matching variant which does have strong theoretical convergence guarantees. However, it relies on a simultaneous, extra-gradient update. IREG-PRM+ is an instance of the more general IR-PRM framework, where empirically optimistic and alternating updates often have better performance. However, the prior extra-gradient analysis does not extend to these cases. We introduce a new approach that covers both settings. For simultaneous and alternating IR-PRM+ in finite two-player zero-sum matrix games, previous-utility prediction recovers the constant-regret and convergence-rate guarantees previously obtained with extra-gradient prediction: external regret bounded independently of T, an O(T^{-1}) average duality gap, and an O(T^{-1/2}) best-current-iterate gap. Moreover, the current duality gap vanishes and the current profile converges to the Nash equilibrium set. The key step bounds the component of consecutive strategy movement not controlled by the existing IR-PRM+ regret inequality using the relative growth of the nondecreasing regret-vector norm rho_t. Coupling this bound across the two players yields recurrences whose effective coefficient scales as 1/(rho_t^X rho_t^Y), preventing unbounded norm growth. We extend the analysis to finitely many simplex learners under a weighted Minty condition and, through the corresponding CFR variant IR-PCFR+, recover analogous guarantees for finite two-player zero-sum perfect-recall extensive-form games under the same full-reach condition as prior work.
• Abstract（参考訳）: レグレトマッチング(およびその変種)と反ファクト的後悔の最小化(英語版)は、通常型および広範な形式のゲーム解決の実践において中心的なアルゴリズムである。 しかし、これらは歴史的に、楽観的で過度な手法で利用できる強力な理論収束保証を欠いていた。 最近の研究でIREG-PRM+が導入された。 しかし、これは同時に、段階的なアップデートに依存している。 IREG-PRM+はより一般的なIR-PRMフレームワークの例である。 しかし、事前の漸進解析はこれらのケースには及ばない。 両方の設定をカバーする新しいアプローチを導入します。 有限2プレーヤゼロサム行列ゲームにおけるIR-PRM+の同時および交互化のために、事前効用予測は、T から独立に有界な外的後悔、O(T^{-1}) 平均双対性ギャップ、O(T^{-1/2}) 最短電流配位ギャップといった、以前に得られた定数と収束率の保証を回復する。 さらに、電流双対性ギャップは消滅し、電流プロファイルはナッシュ平衡集合に収束する。 鍵ステップは、非減少後悔ベクトルノルムrho_tの相対的な成長を用いて、既存のIR−PRM+後悔不平等によって制御されない連続戦略運動の成分を束縛する。 この境界を2つのプレイヤーに結合すると、有効係数が1/(rho_t^X rho_t^Y)となり、非有界なノルム成長を防ぐ。 重み付きMinty条件下で有限個の単純学習者に解析を拡張し、対応するCFR変種IR-PCFR+を通して、前処理と同じフルリーチ条件下での有限2プレイヤーゼロサム完全リコール広義ゲームに対する類似保証を復元する。

関連論文リスト

• Unregularized Linear Convergence in Zero-Sum Game from Preference Feedback [50.89125374999765]
  NLHFにおける最適乗算重み更新(mathtOMWU$)に対する最初の収束保証を提供する。 本分析では, 稀に発生する行動の確率が指数関数的に小さい値から指数関数的に増大する新たな限界収束挙動を同定する。
  論文  参考訳（メタデータ） (2025-12-31T12:08:29Z)
• 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 in Monotone Mean Field Games [24.486052525745574]
  平均場ゲーム(MFG)は、無限個のエージェント間の相互作用をモデル化する。 既存のアルゴリズムは厳密な単調性を必要とするか、平均的な反復の収束を保証するだけである。 本稿では,少数のMDステップによるPP更新を概ね実装した近似プロキシ・ポイント(mathtAPP$)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-10-07T15:28:18Z)
• 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)
• Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent [119.5481797273995]
  FTRL (Follow-the-regularized-leader) とオンラインミラー降下 (OMD) は、オンライン凸最適化における最も一般的な後悔の最小化手法である。 RMとRM+はFTRLとOMDをそれぞれ実行し、ブラックウェルのアプローチ性ゲームにおいて、ハーフスペースを常に強制的に選択するアルゴリズムであることを示す。 18の共通ゼロサムワイドフォームベンチマークゲームを対象とした実験では,予測的RM+と反ファクト的後悔の最小化が,最速のアルゴリズムよりもはるかに高速に収束することを示した。
  論文  参考訳（メタデータ） (2020-07-28T16:49:55Z)
• 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)

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

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