Asymmetric Perturbation in Solving Bilinear Saddle-Point Optimization

2025/06/06 by Kenshi Abe, Abe, Kenshi, Mitsuki Sakamoto +5
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2506.05747

openalex publication_date 2025/06/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• LiteEFG: An Efficient Python Library for Solving Extensive-form Games
• Fundamental Benefit of Alternating Updates in Minimax Optimization
• Online Iterative Reinforcement Learning from Human Feedback with General Preference Model
• Nash Learning from Human Feedback
• Adaptively Perturbed Mirror Descent for Learning in Games
• Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback
• Asymptotic Convergence and Performance of Multi-Agent Q-Learning Dynamics
• Symmetric (Optimistic) Natural Policy Gradient for Multi-agent Learning with Parameter Convergence
• Mastering the Game of No-Press Diplomacy via Human-Regularized Reinforcement Learning and Planning
• Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games
• Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Games
• Last-iterate Convergence to Trembling-hand Perfect Equilibria
• Optimistic Gradient Descent Ascent in Zero-Sum and General-Sum Bilinear Games
• Mastering the game of Stratego with model-free multiagent reinforcement learning
• The Power of Regularization in Solving Extensive-Form Games
• Mutation-Driven Follow the Regularized Leader for Last-Iterate Convergence in Zero-Sum Games
• A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Games
• Last-iterate Convergence in Extensive-Form Games
• Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization
• Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization
• From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization
• Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes
• Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems
• Optimistic Regret Minimization for Extensive-Form Games via Dilated\n Distance-Generating Functions
• OpenSpiel: A Framework for Reinforcement Learning in Games
• Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games
• Learning Nash Equilibria in Monotone Games
• A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach
• Solving Imperfect-Information Games via Discounted Regret Minimization
• Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
• Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization
• A Variational Inequality Perspective on Generative Adversarial Networks
• Training GANs with Optimism
• Cycles in adversarial regularized learning
• Learning in games with continuous action sets and unknown payoff functions
• Solving Large Imperfect Information Games Using CFR+
• Optimization, Learning, and Games with Predictable Sequences
• Online Learning with Predictable Sequences
• Geometrical and analytical characteristic properties of piecewise affine mappings
• Выпуклая оптимизация
• Smooth minimization of non-smooth functions
• Zur Theorie der Gesellschaftsspiele
• Convergence of log(1/ε) for Gradient-Based Algorithms in Zero-Sum Games without the Condition Number: A Smoothed Analysis

Related

• A Robust Framework for Analyzing Gradient-Based Dynamics in Bilinear Games
• Statistical Mechanics of Min-Max Problems
• Linear Last-iterate Convergence in Constrained Saddle-point Optimization
• An implicit gradient-descent procedure for minimax problems
• Solving Zero-Sum Games through Alternating Projections