Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games
Authors: Yang Cai, Gabriele Farina, Julien Grand-Clément, Christian Kroer, Chung-Wei Lee, Haipeng Luo, Weiqiang Zheng
ICLR 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We start by showing numerically that several variants used in practice, such as RM+, predictive RM+ and alternating RM+, all lack last-iterate convergence guarantees even on a simple 3 3 matrix game. We then prove that recent variants of these algorithms based on a smoothing technique, extragradient RM+ and smooth Predictive RM+, enjoy asymptotic last-iterate convergence (without a rate), 1/ t best-iterate convergence, and when combined with restarting, linear-rate last-iterate convergence. 4. Experiments. We validate the last-iterate convergence of Ex RM+ and SPRM+ (including their restarted variants that we propose) numerically on four instances of matrix games, including Kuhn poker and Goofspiel. |
| Researcher Affiliation | Academia | Yang Cai Yale EMAIL Gabriele Farina MIT EMAIL Julien Grand-Clément HEC Paris EMAIL Christian Kroer Columbia EMAIL Chung-Wei Lee USC EMAIL Haipeng Luo USC EMAIL Weiqiang Zheng Yale EMAIL |
| Pseudocode | Yes | Algorithm 1 Regret Matching+ (RM+)... Algorithm 2 Predictive RM+ (PRM+)... Algorithm 3 Extragradient RM+ (Ex RM+)... Algorithm 4 Smooth PRM+ (SPRM+)... Algorithm 5 Restarting Ex RM+ (RS-Ex RM+)... Algorithm 6 Restarting SPRM+ (RS-SPRM+)... Algorithm 7 Alternating RM+ (alt. RM+)... Algorithm 8 Alternating Predictive RM+ (alt. PRM+)... Algorithm 9 Extragradient algorithm (EG)... Algorithm 10 Optimistic gradient descent (OG) |
| Open Source Code | No | No explicit statement or link for open-source code release is provided in the paper. The paper mentions the algorithms were coded in Python 3.8.8 for the numerical experiments, but does not offer access to the implementation. |
| Open Datasets | Yes | We use the 3x3 matrix game instance from Section 3, the normal-form representations of Kuhn poker and Goofspiel, as well as 25 random matrix games of size (d1, d2) = (10, 15)... Kuhn poker is a widely used benchmark game introduced by Kuhn (1950)... We use an imperfect-information variant of the standard benchmark game introduced by Ross (1971)... The coefficients of the matrices are normally distributed with mean 0 and variance 1 and are sampled using the numpy.random.normal function from the numpy Python package (Harris et al., 2020). |
| Dataset Splits | No | The paper analyzes algorithms for solving matrix games and mentions specific game instances (3x3 matrix game, Kuhn poker, Goofspiel, random matrix games) but does not describe any training/test/validation dataset splits, as these are typically not applicable to the problem of solving a single game instance. Evaluation is performed on the full game definitions. |
| Hardware Specification | Yes | All the algorithms were coded with Python 3.8.8, and we ran our numerical experiments on a laptop with 2.2 GHz Intel Core i7 and 8 GB of RAM. |
| Software Dependencies | Yes | All the algorithms were coded with Python 3.8.8... The coefficients of the matrices are normally distributed with mean 0 and variance 1 and are sampled using the numpy.random.normal function from the numpy Python package (Harris et al., 2020). |
| Experiment Setup | Yes | For the algorithms requiring a stepsize (Ex RM+, SPRM+, EG and OG), we choose the best stepsizes η {1, 10 1, 10 2, 10 3, 10 4}. We initialize all algorithms at ((1/d1)1d1, (1/d2)1d2). We present our results when choosing a stepsize η = 0.05 in Figure 7 and Figure 8. |