Non-Asymptotic Last-Iterate Convergence for Scale-Invariant Regret-Matching Algorithms in Matrix Games

Regret matching (RM) is a widely used no-regret learning paradigm for computing a Nash Equilibrium (NE) in games, best known for its parameter-free and scale-invariant properties. However, these desirable properties have so far been difficult to reconcile with last-iterate convergence: classical scale-invariant RM variants may exhibit cycling, whereas existing convergent RM methods typically introduce additional step size or smoothing parameters to stabilize the learning dynamics, thereby sacrificing scale invariance. In this work, we take a step toward closing this gap by introducing a scale-invariant RM-type algorithm, termed Radial IREG-PRM${}^{+}$, with non-asymptotic last-iterate convergence guarantees in two-player zero-sum matrix games. The key idea is to apply a deterministic radial expansion with exponent $\alpha \in (0,1/2)$ to the (pseudo-)cumulative regret vector while leaving the induced strategy unchanged. For arbitrary bounded utility sequences, Radial IREG-PRM${}^{+}$ achieves the optimal $O(\sqrt{T})$ adversarial cumulative regret for every fixed $\alpha$, without prior knowledge of either the horizon or the utility scale. In self-play, a radially weighted RVU-bound analysis further yields an $O(T^{-1+\alpha })$ average-iterate convergence rate, which can be made arbitrarily close to the optimal $O(T^{-1})$ rate. More importantly, we establish an explicit, instance-dependent stretched-exponential last-iterate rate of $O(e^{-c{T}^{1-2\alpha }})$ for some game-dependent constant $c>0$. We complement this fast instance-dependent guarantee with a uniform worst-case lower bound of $\Omega (T^{-1+\alpha })$ over normalized matrix games, together with a matching $O(T^{-1+\alpha })$ upper bound for the case in which exactly one player never gets non-zero cumulative regrets. Finally, we extend Radial IREG-PRM${}^{+}$ to the single-sample bandit-feedback setting by using regularization technique, and establish an in-expectation last-iterate convergence rate of $O(T^{-1/10+\epsilon })$ for any $\epsilon \in (0,1/10)$. Experiments on four instances of matrix games further validate the competitiveness of Radial IREG-PRM${}^{+}$ over existing baselines.