Last-Iterate Convergence of Regularized Gradient Methods for Stochastic Monotone Variational Inequalities

We study last-iterate convergence for stochastic smooth and monotone variational inequalities (VIs), a framework that captures convex-concave saddle points and Nash equilibrium computation in monotone games with noisy payoff feedback. In contrast to the well-understood average-iterate guarantees, anytime last-iterate guarantees in stochastic settings remain limited, despite their relevance for uncoupled learning dynamics that output a single current strategy. We analyze two single-call regularized methods, the \emph{regularized gradient (RG)} and the \emph{regularized optimistic gradient (ROG)} methods, and establish anytime last-iterate convergence rates in terms of the squared gap function. For monotone VIs, RG attains $O(t^{-2/5})$ while ROG achieves the variance-adaptive rate $O(\sigma^{4/5} t^{-2/5} + t^{-1})$, where $\sigma^2$ is the noise variance. For $\lambda$-strongly monotone VIs, ROG yields $O(\sigma^2 / (\lambda^2 t) + t^{-c})$ for any constant $c \ge 2$. These results give anytime last-iterate guarantees without knowing the horizon and show that optimism improves convergence in the low-noise regime.

When multiple AI agents interact (for example, in games or in training generative AI), they often need to settle toward a stable equilibrium. A core challenge is making the current strategy good at every moment, not just on average, since each player must act now. This becomes much harder when the feedback signals are noisy, as is typical in real systems. We study two simple algorithms that update once per round from noisy feedback, and prove they steer the current strategy toward equilibrium. Crucially, our guarantees hold at every step, without knowing in advance how long the process will run. We achieve this through a careful balance of a shrinking pull toward a reference point and a decreasing step size. Earlier work either required knowing the run time up front or only guaranteed averages rather than the current state. Our results show that simple, natural algorithms suffice for the harder problem of staying close to equilibrium at any time. The guarantees even sharpen when the noise level is small. This may inform learning rules for AI systems with multiple interacting agents, such as in strategic games or setups where models compete and improve each other.