Faster Last-Iterate Convergence for Zero-Sum Games with Stochastic Feedback via Anchor-Regularized Learning

We study uncoupled learning in two-player zero-sum matrix games under stochastic feedback. Each player updates from only its own feedback, without observing the opponent's action, strategy, or payoffs. We propose anchor-regularized follow-the-regularized-leader (AR-FTRL), which repeatedly solves the game regularized toward an anchor strategy profile, updating the anchor to each solution. As a warm-up, under unbiased noisy gradients with bounded second moment, the $L^2$ norm of the gap of the last strategy converges at rate $\tilde{\mathcal{O}}(T^{-1/2})$. This guarantee exploits the metric subregularity of the zero-sum game's bilinear structure, under which the regularized equilibrium contracts toward the Nash equilibrium set by a constant factor at each anchor update. Our main result extends this to bandit feedback, where each player observes only the scalar payoff of its sampled action. Under a unique fully mixed Nash equilibrium, the $L^2$ norm of the gap of the last strategy converges at the same $\tilde{\mathcal{O}}(T^{-1/2})$ rate after $T$ observations, even though the importance-weighted gradient estimator has unbounded second moment near the boundary of the simplex. Both guarantees hold only at the anchor updates, not at every round. Under bandit feedback, this yields a faster rate than the $\tilde{\mathcal{O}}(t^{-1/4})$ of every-round guarantees, though the guarantee is no longer anytime.