arXiv：cs.LG· Michael Sullins, Ian A. Kash·· 3 小时前
IR-PRM+ 用前效用预测实现恒定 regret 与最优迭代收敛
IR-PRM+ with Previous-Utility Prediction: Constant Regret and Best-Iterate Convergence
AI 导读
IR-PRM+ 通过前效用预测，在同时与交替更新的有限两人零和矩阵博弈中恢复了此前仅靠额外梯度预测才有的收敛保证：外部 regret 不随 T 增长、平均对偶间隙为 O(T^{-1})、最优当前迭代间隙为 O(T^{-1/2})，且当前对偶间隙趋于消失、策略收敛到 Nash 均衡集。
正文
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.
| Subjects: | Machine Learning (cs.LG); Computer Science and Game Theory (cs.GT) |
| Cite as: | arXiv:2610.19016 [cs.LG] |
| (or arXiv:2610.19016v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.19016 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Michael Sullins [view email]
[v1]
Tue, 13 Oct 2026 18:10:11 UTC (61 KB)
来源：arXiv：cs.LG · arxiv.org