遗憾匹配终于有强收敛保证了！同步交替都搞定，恒定遗憾+纳什均衡收敛
IR-PRM+ with Previous-Utility Prediction: Constant Regret and Best-Iterate Convergence
📖 AI 总结
该论文研究博弈求解中遗憾匹配类算法的理论收敛性。此前工作提出的IREG-PRM+虽具备强收敛保证，但依赖同步的额外梯度更新，无法覆盖实践中表现更优的乐观与交替更新情形。作者提出"前序效用预测"这一新方法，统一处理同步与交替两种IR-PRM+变体。在有限二人零和矩阵博弈中，该方法恢复了此前仅由额外梯度预测获得的保证：外部遗憾与时间T无关，平均对偶间隙为O(T^{-1})，最优当前迭代间隙为O(T^{-1/2})，且当前对偶间隙趋于零、策略收敛至纳什均衡集。关键技术在于用非递减遗憾向量范数的相对增长来约束策略移动中未被现有不等式控制的部分，并将双方约束耦合，使有效系数按1/(rho_t^X rho_t^Y)缩放，从而防止范数无界增长。作者进一步将分析推广至加权Minty条件下的有限单纯形学习器，并通过对应的CFR变体IR-PCFR+，在相同完全可达条件下为有限二人零和完美回忆扩展式博弈获得类似保证。
🔑 关键词速览
| Regret Matching | 一种用于博弈论和在线学习的策略选择方法，根据历史遗憾值按比例选择动作。 |
| Counterfactual Regret Minimization (CFR) | 一种用于求解扩展型博弈的迭代算法，通过最小化反事实遗憾来逼近纳什均衡。 |
| Extra-gradient | 一种优化方法，通过预测下一步梯度来更新参数，常用于求解鞍点问题。 |
| Duality Gap | 衡量当前策略与最优策略之间差距的指标，在零和博弈中反映收敛程度。 |
| Nash Equilibrium | 博弈论中的一种稳定状态，其中任何玩家都无法通过单方面改变策略来获得更好的收益。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅