Asymmetric Perturbation in Solving Bilinear Saddle-Point Optimization

This paper proposes asymmetric perturbation, where only one player's payoff function is perturbed, for solving bilinear saddle-point optimization problems, commonly arising in minimax problems, game theory, and constrained optimization. Symmetric perturbation is known to require decreasing its strength to ensure convergence to a solution, i.e., an equilibrium in the original game, resulting in a slower rate. First, with asymmetric perturbation, we show that, for a sufficiently small perturbation strength, the equilibrium strategy of the asymmetrically perturbed game coincides with an equilibrium strategy of the original unperturbed game. Second, building on this coincidence, we construct a learning algorithm with a linear last-iterate convergence rate. Third, motivated by the fact that the coincidence relies on the perturbation strength being sufficiently small, we also provide a parameter-free variant, retaining the linear rate. Finally, we empirically demonstrate fast convergence toward equilibria in both normal-form and extensive-form games.

Many machine learning problems reduce to a saddle-point (minimax) problem: two players with opposing objectives, where the goal is a Nash equilibrium that neither player can improve upon by deviating. The catch is that the learned strategies often cycle instead of converging, so this last-iterate convergence fails even in simple cases. A widely used remedy adds a payoff perturbation—a small penalty on both players that stabilizes the dynamics. But this symmetric perturbation shifts the equilibrium away from the original game in proportion to its strength, so the strength must be decreased on a careful schedule, which slows convergence. We propose asymmetric perturbation: penalize only one player's payoff. We prove that, as long as the perturbation strength is small enough, the equilibrium of the perturbed game exactly coincides with an equilibrium of the original game—no shifting, no decreasing schedule. Building on this invariance, we design AsymP-GDA, which attains a linear last-iterate convergence rate, and a parameter-free variant that keeps this rate without knowing the allowable strength. This breaks the usual trade-off between accuracy and speed. On normal-form and extensive-form games—including poker benchmarks—our method converges fast and lands directly on an equilibrium, pointing toward more reliable equilibrium computation in large-scale competitive learning.