IR-PRM+ with Previous-Utility Prediction: Constant Regret and Best-Iterate Convergence

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.